package 动态规划

/*
https://leetcode.cn/studyplan/top-100-liked/

32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：
输入：s = ""
输出：0
*/

func longestValidParentheses(s string) int {
	res := 0     //结果长度
	var st []int //初始化栈, 并将-1加入栈中
	st = append(st, -1)

	for i := 0; i < len(s); i++ {
		if s[i] == '(' { //如果是左括号,直接入栈
			st = append(st, i)
		} else { //如果是右括号, 弹出栈顶元素
			st = st[:len(st)-1]
			if len(st) == 0 { //如果栈为空了,直接将当前下标入栈
				st = append(st, i)
			} else { //否则不为空,就是构成了有效的括号, 更新最长计数
				res = max(res, i-st[len(st)-1])
			}
		}
	}
	return res
}
